
# This is an extremely simple chess like speed test program written in Python
# This program can be distributed under GNU General Public License Version 2.
# (C) Jyrki Alakuijala 2005
#
# Despite its looks, this program was written in Python, not converted to it.
# This program is incomplete, castlings, enpassant situation etc. are not properly implemented
# game ending is not recognized. The evaluator as simple as it ever could be. 
#
# The board is an 160-element array of ints, Nones and Booleans,
# The board contains the real board in squares indexed in variable 'squares'
# The oversized board is to allow for "0x88" chess programming trick for move generation.
# Other board data:
# 4x castling flags, indices [10-13], queen side white, king side white, queen side black, king side white
# turn, enpassant [26, 27]

from copy import copy

iNone = -999
iTrue = 1
iFalse = 0

setup = (4, 2, 3, 5, 6, 3, 2, 4, iNone, iNone) + (iTrue,)*4 + (iNone, iNone) +   (1,) * 8 + (iNone, iNone, iTrue, iNone, iNone, iNone, iNone, iNone,) +   ((0, ) * 8 + (iNone,) * 8) * 4 +   (-1,) * 8 + (iNone,) * 8 +   (-4, -2, -3, -5, -6, -3, -2, -4) + (iNone,) * 40

squares = tuple([i for i in range(128) if not i & 8])
knightMoves = (-33, -31, -18, -14, 14, 18, 31, 33)
bishopLines = (tuple(range(17, 120, 17)), tuple(range(-17, -120, -17)), tuple(range(15, 106, 15)), tuple(range(-15, -106, -15)))
rookLines = (tuple(range(1, 8)), tuple(range(-1, -8, -1)), tuple(range(16, 128, 16)), tuple(range(-16, -128, -16)))
queenLines = bishopLines + rookLines
kingMoves = (-17, -16, -15, -1, 1, 15, 16, 17)

linePieces = ((), (), (), bishopLines, rookLines, queenLines, (), (), queenLines, rookLines, bishopLines, (), ())

clearCastlingOpportunities = [None] * 0x80
for (i, v) in ((0x0, (10,)), (0x4, (10, 11)), (0x7, (11,)), (0x70, (12,)), (0x74, (12, 13)), (0x77, (13,))):
  clearCastlingOpportunities[i] = v

pieces = ".pnbrqkKQRBNP"

def evaluate(board):
  evals = (0, 100, 300, 330, 510, 950, 100000, -100000, -950, -510, -330, -300, -100)
  return sum([evals[board[i]] for i in squares])

#def printBoard(board):
#  for i in range(7,-1,-1):
#    for j in range(8):
#      ix = i * 16 + j
#      print((pieces[board[ix]]))
#    print()

def move(board, mv):
  ix = (mv >> 8) & 0xff
  board[mv & 0xff] = board[ix]
  board[ix] = 0
  if clearCastlingOpportunities[ix]:
    for i in clearCastlingOpportunities[ix]:
      board[i] = iFalse

  board[26] = int(not board[26]) # Turn
  if (mv & 0x7fff0000) == 0:
    return
  if (mv & 0x01000000): # double step
    board[27] = mv & 7
  else:
    board[27] = iNone # no enpassant
  if (mv & 0x04000000): # castling
    toix = mv & 0xff
    if toix == 0x02:
      board[0x00] = 0
      board[0x03] = 4
    elif toix == 0x06:
      board[0x07] = 0
      board[0x05] = 4
    elif toix == 0x72:
      board[0x70] = 0
      board[0x73] = -4
    elif toix == 0x76:
      board[0x77] = 0
      board[0x75] = -4
    else:
      raise "faulty castling"
  if mv & 0x08000000: # enpassant capture
    if board[26]: # turn after this move
      board[mv & 0x07 + 64] = 0
    else:
      board[mv & 0x07 + 48] = 0
  if mv & 0x10000000: # promotion
    a = (mv & 0xff0000) >> 16
    if (a >= 0x80):
      a = a - 0x100 
    board[mv & 0xff] = a

def toString(move):
  fr = (move >> 8) & 0xff
  to = move & 0xff
  letters = "abcdefgh"
  numbers = "12345678"
  mid = "-"
  if (move & 0x04000000):
    if (move & 0x7) == 0x02:
      return "O-O-O"
    else:
      return "O-O"
  if move & 0x02000000:
    mid = "x"
  retval = letters[fr & 7] + numbers[fr >> 4] + mid + letters[to & 7] + numbers[to >> 4]
  return retval

def moveStr(board, strMove):
  moves = pseudoLegalMoves(board)
  for m in moves:
    if strMove == toString(m):
      move(board, m)
      return
  for m in moves:
    print((toString(m)))
  raise "no move found" #, strMove

def rowAttack(board, attackers, ix, dir):
  own = attackers[0]
  for k in [i + ix for i in dir]:
    if k & 0x88:
      return False
    if board[k]:
      return (board[k] * own < 0) and board[k] in attackers

def nonpawnAttacks(board, ix, color):
  return (max([board[ix + i] == color * 2 for i in knightMoves]) or 
          max([rowAttack(board, (color * 3, color * 5), ix, bishopLine) for bishopLine in bishopLines]) or
          max([rowAttack(board, (color * 4, color * 5), ix, rookLine) for rookLine in rookLines]))

nonpawnBlackAttacks = lambda board, ix: nonpawnAttacks(board, ix, -1)
nonpawnWhiteAttacks = lambda board, ix: nonpawnAttacks(board, ix, 1)

def pseudoLegalMovesWhite(board):
  retval = pseudoLegalCapturesWhite(board)
  for sq in squares:
    b = board[sq]
    if b >= 1:
      if b == 1 and not (sq + 16 & 0x88) and board[sq + 16] == 0:
        if sq >= 16 and sq < 32 and board[sq + 32] == 0:
          retval.append(sq * 0x101 + 32)
        retval.append(sq * 0x101 + 16)
      elif b == 2:
        for k in knightMoves:
          if board[k + sq] == 0:
            retval.append(sq * 0x101 + k)
      elif b == 3 or b == 5:
        for line in bishopLines:
          for k in line:
            if (k + sq & 0x88) or board[k + sq] != 0:
              break
            retval.append(sq * 0x101 + k)
      if b == 4 or b == 5:
        for line in rookLines:
          for k in line:
            if (k + sq & 0x88) or board[k + sq] != 0:
              break
            retval.append(sq * 0x101 + k)
      elif b == 6:
        for k in kingMoves:
          if not (k + sq & 0x88) and board[k + sq] == 0:
            retval.append(sq * 0x101 + k)
  if (board[10] and board[1] == 0 and board[2] == 0 and board[3] == 0 and
      -1 not in board[17:22] and
      not nonpawnBlackAttacks(board, 2) and not nonpawnBlackAttacks(board, 3) and not nonpawnBlackAttacks(board, 4)):
    retval.append(0x04000000 + 4 * 0x101 - 2)
  if (board[11] and board[5] == 0 and board[6] == 0 and
      -1 not in board[19:24] and
      not nonpawnBlackAttacks(board, 4) and not nonpawnBlackAttacks(board, 5) and not nonpawnBlackAttacks(board, 6)):
    retval.append(0x04000000 + 4 * 0x101 + 2)
  return retval

def pseudoLegalMovesBlack(board):
  retval = pseudoLegalCapturesBlack(board)
  for sq in squares:
    b = board[sq]
    if b < 0:
      if b == -1 and not (sq + 16 & 0x88) and board[sq - 16] == 0:
        if sq >= 96 and sq < 112 and board[sq - 32] == 0:
          retval.append(sq * 0x101 - 32)
        retval.append(sq * 0x101 - 16)
      elif b == -2:
        for k in knightMoves:
          if board[k + sq] == 0:
            retval.append(sq * 0x101 + k)
      elif b == -3 or b == -5: 
        for line in bishopLines:
          for k in line:
            if (k + sq & 0x88) or board[k + sq] != 0:
              break
            retval.append(sq * 0x101 + k)

      if b == -4 or b == -5:
        for line in rookLines:
          for k in line:
            if (k + sq & 0x88) or board[k + sq] != 0:
              break
            retval.append(sq * 0x101 + k)
      elif b == -6: 
        for k in kingMoves:
          if not (k + sq & 0x88) and board[k + sq] == 0:
            retval.append(sq * 0x101 + k)
  if (board[12] and board[0x71] == 0 and board[0x72] == 0 and board[0x73] == 0 and
      1 not in board[0x61:0x65] and
      not nonpawnWhiteAttacks(board, 0x72) and not nonpawnWhiteAttacks(board, 0x73) and not nonpawnWhiteAttacks(board, 0x74)):
    retval.append(0x04000000 + 0x74 * 0x101 - 2)
  if (board[11] and board[0x75] == 0 and board[0x76] == 0 and
      -1 not in board[0x63:0x68] and
      not nonpawnWhiteAttacks(board, 0x74) and not nonpawnWhiteAttacks(board, 0x75) and not nonpawnWhiteAttacks(board, 0x76)):
    retval.append(0x04000000 + 0x74 * 0x101 + 2)
  return retval

def pseudoLegalMoves(board):
  if board[26]:
    return pseudoLegalMovesWhite(board)
  else:
    return pseudoLegalMovesBlack(board)

def pseudoLegalCapturesWhite(board):
  retval = []
  for sq in squares:
    b = board[sq]
    if b >= 1:
      if b == 1: 
        if not (sq + 17 & 0x88) and board[sq + 17] < 0:
          retval.append(0x02000000 + sq * 0x101 + 17)
        if not (sq + 15 & 0x88) and board[sq + 15] < 0:
          retval.append(0x02000000 + sq * 0x101 + 15)
        if sq >= 64 and sq < 72 and abs((sq & 7) - board[27]) == 1: # enpassant
          retval.append(0x02000000 + sq * 0x100 + (sq & 0x70) + 16 + board[27])
      elif b == 2:
        for k in knightMoves:
          if not (sq + k & 0x88) and board[k + sq] < 0:
            retval.append(0x02000000 + sq * 0x101 + k)
      elif b == 6:
        for k in kingMoves:
          if not(k + sq & 0x88) and board[k + sq] < 0:
            retval.append(0x02000000 + sq * 0x101 + k)
      else:
        for line in linePieces[b]:
          for k in line:
            if (sq + k & 0x88) or board[k + sq] >= 1:
              break
            if board[k + sq] < 0:
              retval.append(0x02000000 + sq * 0x101 + k)
              break
  return retval

def pseudoLegalCapturesBlack(board):
  retval = []
  for sq in squares:
    b = board[sq]
    if b < 0:
      if b == -1: 
        if board[sq - 17] >= 1:
          retval.append(0x02000000 + sq * 0x101 - 17)
        if board[sq - 15] >= 1:
          retval.append(0x02000000 + sq * 0x101 - 15)
        if sq >= 48 and sq < 56 and abs((sq & 7) - board[27]) == 1: # enpassant
          retval.append(0x0a000000 + sq * 0x100 + (sq & 0x70) - 16 + board[27])
      elif b == -2:
        for k in knightMoves:
          if not (sq + k & 0x88) and board[k + sq] >= 1:
            retval.append(0x02000000 + sq * 0x101 + k)
      elif b == -3:
        for line in bishopLines:
          for k in line:
            if board[k + sq] < 0:
              break
            if board[k + sq] >= 1:
              retval.append(0x02000000 + sq * 0x101 + k)
              break
      elif b == -4:
        for line in rookLines:
          for k in line:
            if board[k + sq] < 0:
              break
            if board[k + sq] >= 1:
              retval.append(0x02000000 + sq * 0x101 + k)
              break
      elif b == -5:
        for line in queenLines:
          for k in line:
            if board[k + sq] < 0:
              break
            if board[k + sq] >= 1:
              retval.append(0x02000000 + sq * 0x101 + k)
              break
      elif b == -6:
        for k in kingMoves:
          if board[k + sq] >= 1:
            retval.append(0x02000000 + sq * 0x101 + k)
  return retval

def pseudoLegalCaptures(board):
  if board[26]:
    return pseudoLegalCapturesWhite(board)
  else:
    return pseudoLegalCapturesBlack(board)

def legalMoves(board):
  allMoves = pseudoLegalMoves(board)
  retval = []
  #from copy import copy
  kingVal = 6
  if board[26]:
    kingVal = -kingVal
  for mv in allMoves:
    board2 = copy(board)
    move(board2, mv)
    #print "trying to reduce move", toString(mv)
    if not [i for i in pseudoLegalCaptures(board2) if board2[i & 0xff] == kingVal]:
      retval.append(mv)
  return retval

def alphaBetaQui(board, alpha, beta, n):
  e = evaluate(board)
  if not board[26]:
    e = -e
  if e >= beta:
    return (beta, iNone) # XXX
  if (e > alpha): 
    alpha = e
  bestMove = iNone # XXX
  if n >= -4:
    #from copy import copy
    for mv in pseudoLegalCaptures(board):
      newboard = copy(board)
      move(newboard, mv)
      value = alphaBetaQui(newboard, -beta, -alpha, n - 1)
      value = (-value[0], value[1])
      if value[0] >= beta:
        return (beta, mv)
      if (value[0] > alpha):
        alpha = value[0]
        bestMove = mv
  return (alpha, bestMove)

def alphaBeta(board, alpha, beta, n):
  if n == 0:
    return alphaBetaQui(board, alpha, beta, n)
#  from copy import copy
  bestMove = iNone # XXX

  for mv in legalMoves(board):
    newboard = copy(board)
    move(newboard, mv)
    value = alphaBeta(newboard, -beta, -alpha, n - 1)
    value = (-value[0], value[1])
    if value[0] >= beta:
      return (beta, mv)
    if (value[0] > alpha):
      alpha = value[0]
      bestMove = mv
  return (alpha, bestMove)

def speedTest():
  board = list(setup)
  moveStr(board, "c2-c4")
  moveStr(board, "e7-e5")
  moveStr(board, "d2-d4")

  res = alphaBeta(board, -99999999, 99999999, 4)
  print(res)
  moveStr(board, "d7-d6")
  res = alphaBeta(board, -99999999, 99999999, 4)
  print(res)

if __name__ == '__main__':
    speedTest()
